package NC;

import java.util.ArrayList;
import java.util.Arrays;

// 决策树
public class NC27 {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        backtrack(S,0,S.length,new ArrayList<>());
        return ans;
    }
    public void backtrack(int[] S,int start,int k,ArrayList<Integer> temp){
        if(k<0) return;
        ans.add(new ArrayList<>(temp)); //深拷贝
        for (int i = start; i < S.length; i++) {
            temp.add(S[i]);
            backtrack(S,i+1,k-1,temp);
            temp.remove(temp.size()-1);
        }
    }
}

class Test{
    public static void main(String[] args) {
        NC27 nc27 = new NC27();
        System.out.println(nc27.subsets(new int[]{1, 2, 3}));
    }

}